/**
 * 二叉平衡树
 *
 * 1. 根节点的左子树与右子树的高度差不能超过 1
 * 2. 这颗二叉树的每个子树都要符合第一条
 *
 *      是             是              是             不是
 *      A              A              A               A
 *    /   \          /   \          /   \           /   \
 *   B     C        B     C        B     C         B     C
 *  / \   / \      /     / \      / \   / \       /     / \
 * D   E F   G    D     F   G    D   E F   G     D     I   G
 *                              /               /
 *                             H               H
 */

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new TreeNode("A");
const b = new TreeNode("B");
const c = new TreeNode("C");
const d = new TreeNode("D");
const e = new TreeNode("E");
const f = new TreeNode("F");
const g = new TreeNode("G");
const h = new TreeNode("H");
const j = new TreeNode("J");
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.left = h;

//h.left = j;

/**
 * 计算二叉树的最大深度
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {number} 返回二叉树的最大深度
 */
function getDeep(root) {
  // 如果节点为空，则深度为0
  if (root == null) return 0;
  // 递归计算左右子树的最大深度，并取较大值加1
  return Math.max(getDeep(root.left), getDeep(root.right)) + 1;
}

/**
 * 判断二叉树是否平衡
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {boolean} 如果二叉树是平衡的返回true，否则返回false
 */
function isBalance(root) {
  // 如果节点为空，则认为是平衡的
  if (root == null) return true;
  // 计算左子树的深度
  let leftDeep = getDeep(root.left);
  // 计算右子树的深度
  let rightDeep = getDeep(root.right);
  // 如果左右子树深度差超过1，则不平衡
  if (Math.abs(leftDeep - rightDeep) > 1) return false;
  // 递归判断左右子树是否平衡
  return isBalance(root.left) && isBalance(root.right);
}


console.log("▶『isBalance』", isBalance(a));
